演算法

一種愛恨交織的課程

解題目

• 使用 Big O 、 Ω 以及 Θ 的定義，證明 8n^2+12? ∈ ?(?^2)

Let c = 10,
當 n>6, 8n^2+12?<10?^2 恆成立
8n^2+12? ∈ ?(?^2)

Let c = 1,
當 n>0 , 8n^2+12? > ?^2 恆成立
8n^2+12? ∈ Ω(?^2)
因為
8n^2+12? ∈ ?(?^2) ∩ Ω(?^2)
所以
8n^2+12? ∈ ?(?^2)

• 試說明何為 P、何為 NP、何為 NP-complete

P 是所有可以被多項式時間必然式演算法(Polynomial-time deterministic algorithm) 解決之決策問題的集合。
NP 是所有可以被多項式時間非必然式演算法(Polynomial-time deterministic algorithm) 解決之決策問題的集合，即可以由一個多項式時間必然式演算法檢核任意對於該問題解答之猜測是否為正確解。
NP-complete，一個決策問題的集合，且任意屬於該集合之決策問題皆符合下列兩個條件：
(1) 其為 NP
(2) 任意 NP 問題都可以於多項式時間內化約成該集合中的任一問題